import javax.management.StandardEmitterMBean;
import java.util.Arrays;
import java.util.Stack;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 74646
 * Date: 2022-03-15
 * Time: 21:42
 */
public class TestSort {

    /**
     * 时间复杂度：O(N^2)
     *          最好的情况是O(N)：对于直接插入排序来说，最好的情况是数据有序
     *          对于直接插入排序来说，数据越有序，排序速度越快。
     * 空间复杂度：O(1)
     * 稳定性：稳定的
     * @param array
     */
    public static void insertSort2(int[] array,int left,int right){
        for (int i = 1; i < left; i++) {
                int tmp = array[i];
            int index = i-1;
            for (; index >right ; index--) {
                if(array[index]>tmp){
                    array[index+1] = array[index];
                }else{
                    break;
                }
            }
            array[index+1] = tmp;
        }
    }

    public static void insertSort(int[] array){
        for (int i = 1; i < array.length; i++) {
            int tmp = array[i];
            int index = i-1;
            for (; index >0 ; index--) {
                if(array[index]>tmp){
                    array[index+1] = array[index];
                }else{
                    break;
                }
            }
            array[index+1] = tmp;
        }
    }

    /**
     * 直接插入排序
     * @param array 待排序序列
     * @param gap 分的组数
     */
    public static void shell(int[] array,int gap){
        for (int i = 1; i < array.length; i++) {
            int tmp = array[i];
            int j = i-gap;
            for ( ; j >=0 ; j-=gap) {
                if(array[j]>tmp){
                    array[j+gap] = array[j];
                }else{
                    break;
                }
            }
            array[j+gap] = tmp;
        }
    }

    /**
     * 时间复杂度[和增量有关]：O(n^1.3~n^1.5)
     * 空间复杂度：O(1)
     * 稳定性：不稳定
     * @param array
     */
    public static void shellSort(int[] array){
        int gap = array.length;
        while(gap>1){
            shell(array,gap);
            gap /= 2;
        }
        shell(array,1); //对最后一组进行排序
    }

    /**
     * 选择排序
     * 时间复杂度：O(N^2)
     * 空间复杂度：O(1)
     * 稳定性：不稳定
     * @param array 待排序序列
     */
    public static void selectSort(int[] array){
        for(int i=0;i<array.length;i++){
            int minIndex = i;
            for(int j=i+1;j<array.length;j++){
                //找到最小值的下标
                if(array[j]<array[minIndex]){
                    minIndex = j;
                }
            }
            int tmp = array[i];
            array[i] = array[minIndex];
            array[minIndex] = tmp;
        }
    }


    /**
     * 时间复杂度：O(N*log N)
     * 空间复杂度：O(1)
     * 稳定性：不稳定
     * @param array
     */
    public static void heapSort(int[] array){
        //建堆，时间复杂度：O(N)
        createHeap(array);
        int end = array.length-1;
        //交换、调整。时间复杂度O(N*log N)
        while (end>0){
            swap(array,0,end);
            shiftDown(array,0,end);
            end--;
        }
    }

    //向下调整
    public static void shiftDown(int[] array,int parent,int len){
        int child = 2*parent+1; //左孩子下标
        while (child<len){
            if(child+1<len && array[child]<array[child+1]){
                child++;
            }
            //child 下标就是左右孩子的最大值
            if(array[child]>array[parent]){
                swap(array,child,parent);
                parent = child;
                child = 2*parent+1;
            }else{
                break;
            }
        }
    }
    //创建大根堆
    public static void createHeap(int[] array){
        for (int parent = (array.length-1-1)/2; parent >=0; parent--) {
            shiftDown(array,parent,array.length);
        }
    }

    //元素交换
    public static void swap(int[] array,int index1,int index2){
        int tmp = array[index1];
        array[index1] = array[index2];
        array[index2] = tmp;
    }

    /**
     * 冒泡排序
     * @param array 待排序序列
     */
    public static void bubbleSort(int[] array){
        //冒泡排序的趟数
        boolean flag = false; //标记
        for (int i=0;i<array.length-1;i++){
            //每一趟比较的次数
            for (int j = 0; j <array.length-1-i; j++) {
                if(array[j]>array[j+1]){
                    swap(array,j,j+1);
                    flag = true; //如果进行了交换，就将flag置为true
                }
            }
            if(flag==false){ //如果flag 为false，说明上一趟排序的过程中没有元素交换，数组已经有序
                break;
            }
        }
    }

    /**
     * 快速排序
     * 时间复杂度：
     *      最好【基准每次都可以均匀分割待排序序列】O(n*log n)
     *      最坏【数据有序或者逆序】O(n^2)
     * 空间复杂度：
     *      最好：O(log n)
     *      最坏【单分支的树】：O(n)
     * 稳定性：不稳定
     * @param array 待排序序列
     */
    public static void quickSort1(int[] array){
        quick(array,0,array.length-1);
    }

    /**
     * 通过基准值，排序基准左右两边的序列
     * @param array 待排序序列
     * @param left 数组首元素的下标（0）
     * @param right 数组最后一个元素的下标 （len-1）
     */
    public static void quick(int[] array,int left,int right){
        if(left>=right){
            return;
        }
        //如果在排序的过程中，小于某个范围了，就可以使用直接插入排序
        if(right-left+1<5){
            insertSort2(array,left,right);
            return;
        }

        int midValIndex = findmidValInde(array,left,right);
        //将中间值与首元素进行交换
        swap(array,midValIndex,left);

        int pivot = partition(array,left,right); //找基准
//        int pivot = findmidValInde(array,left,right); //找基准
        quick(array,left,pivot-1); //排序小于基准值的区间
        quick(array,pivot+1,right); //排序大于基准值的区间
    }


    public static int findmidValInde1(int[] array,int left,int right){
        int mid = left + ((right-left)>>>1); //int mid = (left+right)/2;
        if(array[left]>array[right]){
            if(array[mid] > array[left]){
                return left;
            }else if(array[mid] < array[right]){
                return right;
            }else {
                return mid;
            }
        }else{
            if(array[mid] < array[left]){
                return left;
            }else if(array[mid] > array[right]){
                return right;
            }else {
                return mid;
            }
        }
    }
    /**
     * 挖坑法找基准：使用三数取中法进行优化
     * 找三个数中，中间大小的值的下标
     * @param array 待排序序列
     * @param left 数组左边界
     * @param right 数组右边界
     * @return 然后三个数中，中间大小值的下标
     */
    public static int findmidValInde(int[] array,int left,int right){
        int mid = left + ((right-left)>>>1); //int mid = (left+right)/2;
            if(array[left]>array[right]){
                if(array[mid] > array[left]){
                    swap(array,left,left);
                }else if(array[mid] < array[right]){
                    swap(array,right,left);
                }else {
                    swap(array,mid,left);
                }
            }else{
                if(array[mid] < array[left]){
                    swap(array,left,left);
                }else if(array[mid] > array[right]){
                    swap(array,right,left);
                }else {
                    swap(array,mid,left);
                }
            }
        int tmp = array[left];
        while (left<right){
            //从最后一个元素开始与基准值进行比较，遇到比基准值大的元素 right 就向前移动
            while (left<right && array[right]>=tmp){
                right--;
            }
            //right 指向的值小于tmp的值，将end指向的元素存放到“坑”中（right下标处为“新挖的坑”）
            array[left] = array[right];
            //从首元素开始与基准值进行比较，遇到比基准值小的元素 left 就向后移动
            while (left<right && array[left]<=tmp){
                left++;
            }
            //left 指向的值大于tmp的值，将left指向的元素存放到“坑”中（left下标处为“新挖的坑”）
            array[right] = array[left];
        }
        //上面的循环结束表示 left 与 right 相遇，将基准值存放到相遇的下标处
        array[left] = tmp;
        return right; //相遇下标即为基准值的下标，返回 left 或 right 都可以
    }

    /**
     * Hoare 法找基准的位置
     * @param array 待排序序列
     * @param left 数组首元素的下标（0）
     * @param right 数组最后一个元素的下标 （len-1）
     * @return 返回基准值的下标
     */
    public static int partition1(int[] array,int left,int right){
        int partindex = array[left]; //将数组首元素设置为基准值，与后面的元素进行比较，寻找基准的位置
        int start = left;
        int end =  right;
        while (start<end){
            //从后向前遍历数组，如果遇到比基准值大的元素，end 就向前移动。（找比基准值小的元素）
            while (start<end && array[end]>=partindex){
                end--;
            }
            //从前向后遍历数组，如果遇到比基准值小的元素，start 就向后移动。（找比基准中大的元素）
            while (start<end){
                while (start<end && array[start]<=partindex){
                    start++;
                }
            }
            //交换两个元素，将比基准值大的元素放到数组的右区间，比基准值小的元素放到数组的区间
            swap(array,start,end);
        }
        //上面的循环结束表示 start 与 end 相遇，将相遇位置的元素与基准值交换
        swap(array,left,start);
        return start; //返回存放基准值的下标
    }
    /**
     * 挖坑法找基准的位置
     * @param array 待排序序列
     * @param start 数组首元素的下标（0）
     * @param end 数组最后一个元素的下标 （len-1）
     * @return 返回基准值的下标
     */
    public static int partition(int[] array,int start,int end){
        int tmp = array[start]; //将基准值存放到tmp中，start （0）下标处为“坑”
        while (start<end){
            //从最后一个元素开始与基准值进行比较，遇到比基准值大的元素 end 就向前移动
            while (start<end && array[end]>=tmp){
                end--;
            }
            //end 指向的值小于tmp的值，将end指向的元素存放到“坑”中（end下标处为“新挖的坑”）
            array[start] = array[end];
            //从首元素开始与基准值进行比较，遇到比基准值小的元素 start 就向后移动
            while (start<end && array[start]<=tmp){
                start++;
            }
            //start 指向的值大于tmp的值，将start指向的元素存放到“坑”中（start下标处为“新挖的坑”）
            array[end] = array[start];
        }
        //上面的循环结束表示 start 与 end 相遇，将基准值存放到相遇的下标处
        array[start] = tmp;
        return start; //相遇下标即为基准值的下标，返回 start 或 end 都可以
    }
//    public static int partition(int[] array,int start,int end){
//        int tmp = array[start]; //将基准值存放到tmp中，start （0）下标处为“坑”
//        while (start<end){ //遍历数组
//            //从最后一个元素开始与基准值进行比较，遇到比基准值大的元素 end 就向前移动
//            while (start<end && array[end]>=tmp){
//                end--;
//            }
//            //end 指向的值小于tmp的值，将end指向的元素存放到“坑”中（end下标处为“新挖的坑”）
//            array[start] = array[end];
//            //从首元素开始与基准值进行比较，遇到比基准值小的元素 start 就向后移动
//            while (start<end && array[start]<=tmp){
//                start++;
//            }
//            //start 指向的值大于tmp的值，将start指向的元素存放到“坑”中（start下标处为“新挖的坑”）
//            array[end] = array[start];
//        }
//        //上面的循环结束表示 start 与 end 相遇，将基准值存放到相遇的下标处
//        array[start] = tmp;
//        return start; //相遇下标即为基准值的下标，返回 start 或 end 都可以
//    }


    /**
     * 非递归实现快速排序
     * @param array 待排序序列
     */
    public static void quickSort(int[] array){
        Stack<Integer> stack = new Stack<>();
        int left = 0;
        int right = array.length-1;
        //找基准
        int pivot = findmidValInde(array,left,right);
        if(left+1<pivot){
            //基准的左边至少有两个元素
            stack.push(left);
            stack.push(pivot-1);
        }
        if(right-1>pivot){
            //基准右边至少有两个元素
            stack.push(pivot+1);
            stack.push(right);
        }
        while (!stack.isEmpty()){
            right = stack.pop();
            left = stack.pop();
            pivot = findmidValInde(array,left,right);
            if(left+1<pivot){
                stack.push(left);
                stack.push(pivot-1);
            }
            if(right-1>pivot){
                stack.push(pivot+1);
                stack.push(right);
            }
        }
    }

    //合并两个有序数组
    public static int[] mergeArray(int[] array1,int[] array2){
        int s1 = 0;
        int s2 = 0;
        int index = 0;
        int e1 = array1.length-1;
        int e2 = array2.length-1;
        int[] newArray = new int[array1.length+array2.length];
       while (s1<=e1 && s2<=e2){
           if(array1[s1]>array2[s2]){
               newArray[index++] = array2[s2++];
           }else {
               newArray[index++] = array1[s1++];
           }
       }
       while (s1<=e1){
           newArray[index++] = array1[s1++];
       }
       while (s2<=e2){
           newArray[index++] = array2[s2++];
       }
       return newArray;
    }

    /**
     * 归并排序
     * 时间复杂度：O(N*logN)
     * 空间复杂度：O(N)
     * 稳定性：稳定
     *如果 array[s1]>=array[s2] 不取等号，就是不稳定的
     * @param array
     */
    public static void mergeSort1(int[] array){
        mergeSortInternal(array,0,array.length-1);
    }
    public static void mergeSortInternal(int[] array,int left,int right){
        if(left>=right){
            return;
        }
        int mid = left+((right-left)>>>1);
        //分解左边
        mergeSortInternal(array,left,mid);
        //分解右边
        mergeSortInternal(array,mid+1,right);
        //合并
        merge(array,left,mid,right);
    }

    /**
     *合并有序序列
     * @param array 待合并的序列
     * @param left 每组序列的左边界
     * @param mid 每组序列的中间下标
     * @param right 每组序列的右边界
     */
    public static void merge(int[] array,int left,int mid,int right){
        int s1 = left;
        int s2 = mid+1;
        int e1 = mid;
        int e2 = right;
        int index = 0;
        int[] newArray = new int[right-left+1];
        while (s1<=e1 && s2<=e2){
            if(array[s1]>=array[s2]){
                newArray[index++] = array[s2++];
            }else {
                newArray[index++] = array[s1++];
            }
        }
        while (s1<=e1){
            newArray[index++] = array[s1++];
        }
        while (s2<=e2){
            newArray[index++] = array[s2++];
        }
        for (int i = 0; i < index; i++) {
            array[i+left] = newArray[i];
        }
    }

    /**
     * 非递归实现归并排序
     * @param array 待排序序列
     */
    public static void mergeSort(int[] array){
        int nums = 1;//每组数据的个数
        while (nums<=array.length){
            //数组没都需要遍历，确定归并的区间
            for(int i=0;i<array.length;i+=nums*2){
                int left = i;
                int mid = left+nums-1;
                //防止越界
                if(mid>=array.length){
                    mid = array.length-1;
                }
                int right = mid+nums;
                //防止越界
                if(right>=array.length){
                    right = array.length-1;
                }
                //下标确定后，进行合并
                merge(array,left,mid,right);
            }
            nums*=2;
        }
    }


    public static void main(String[] args) {
        int[] array  = {2,13,9,4,21,14,97,48,66};
//        int[] arr1 = {1,3,5};
//        int[] arr2 = {2,4,6};
//        int[] ret = mergeArray(arr1,arr2);
//        System.out.println(Arrays.toString(ret));
        //insertSort(array);
        //shellSort(array);
        //selectSort(array);
        //heapSort(array);
        //bubbleSort(array);
//        quickSort(array);
        mergeSort(array);
        System.out.println(Arrays.toString(array));
    }

}
